//----------------------------------------------------------------------------------------------
//	Filename:	PointCloud.cpp
//	Author:		Sandro Spina
//	Date:		27/07/2012
//----------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------
#include "Shape/TreePointCloud.h"
#include "Shape/Sphere.h"

using namespace Illumina::Core;

//----------------------------------------------------------------------------------------------
TreePointCloudStatistics::TreePointCloudStatistics(void) 
	: m_internalNodeCount(0)
	, m_leafNodeCount(0)
	, m_maxTreeDepth(0)
	, m_minTreeDepth(0x7FFFFFFF)
	, m_pointCount(0)
	, m_maxLeafPointCount(0)
	, m_minLeafPointCount(0x7FFFFFFF)
	, m_intersectionCount(0)
{ }
//----------------------------------------------------------------------------------------------
std::string TreePointCloudStatistics::ToString(void) const
{
	return boost::str(boost::format("Internal Nodes : %d \n Leaf Nodes : %d \n Minimum Depth : %d \n Maximum Depth : %d \n Triangles : %d \n Min Tri/Leaf : %d \n Max Tri/Leaf : %d \n I-Tests : %d\n")
		% m_internalNodeCount % m_leafNodeCount 
		% m_minTreeDepth % m_maxTreeDepth 
		% m_pointCount % m_minLeafPointCount % m_maxLeafPointCount 
		% m_intersectionCount);
}
//----------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------
ITreePointCloud::ITreePointCloud(void)
	: IPointCloud()
{ }
//----------------------------------------------------------------------------------------------
ITreePointCloud::ITreePointCloud(const std::string& p_strName)
	: IPointCloud(p_strName)
{ }

//----------------------------------------------------------------------------------------------
// Computes the axis-aligned bounding box for the specified list of triangles.
//----------------------------------------------------------------------------------------------
void ITreePointCloud::ComputeBounds(const List<int> &p_objectList, 
	AxisAlignedBoundingBox &p_aabb, float p_fMinEpsilon, float p_fMaxEpsilon)
{
	p_aabb.Invalidate();
	int count = p_objectList.Size();

	if (count > 0) {
		VertexP *pVertex = &(m_pointList[p_objectList.Front()].m_vertex);
		p_aabb.SetExtents(pVertex->Position, pVertex->Position);

		for (int nIdx = 1; nIdx < count; nIdx++) {
			pVertex = &(m_pointList[nIdx].m_vertex);
			p_aabb.Union(pVertex->Position);
		}
	}

	p_aabb.SetMinExtent(p_aabb.GetMinExtent() - Vector3(m_fSphereRadius) - p_fMinEpsilon);
	p_aabb.SetMaxExtent(p_aabb.GetMaxExtent() + Vector3(m_fSphereRadius) + p_fMaxEpsilon);
	
}

//----------------------------------------------------------------------------------------------
// Computes the axis-aligned bounding box for a range of points in pointList.
//----------------------------------------------------------------------------------------------
void ITreePointCloud::ComputeBounds(int p_from, int p_to,
	AxisAlignedBoundingBox &p_aabb, float p_fMinEpsilon, float p_fMaxEpsilon)
{
	p_aabb.Invalidate();
	int size = m_pointList.size();
	if (size > p_to-1) {
		VertexP *pVertex = &(m_pointList[p_from].m_vertex);
		p_aabb.SetExtents(pVertex->Position, pVertex->Position);

		for (int nIdx = p_from; nIdx < p_to; nIdx++) {
			pVertex = &(m_pointList[nIdx].m_vertex);
			p_aabb.Union(pVertex->Position);
		}
	}

	p_aabb.SetMinExtent(p_aabb.GetMinExtent() - Vector3(m_fSphereRadius) - p_fMinEpsilon);
	p_aabb.SetMaxExtent(p_aabb.GetMaxExtent() + Vector3(m_fSphereRadius) + p_fMaxEpsilon);	
}

//----------------------------------------------------------------------------------------------
// Distributes the provided point list between two objects depending on the partitioning
// specified by the parameters (Axis, Partition).
//----------------------------------------------------------------------------------------------
int ITreePointCloud::DistributeUnique(const List<int> &p_objectList, float p_fPartition,
	int p_nAxis, List<int> &p_outLeftList, List<int> &p_outRightList)
{
	int count = (int)p_objectList.Size();
	
	for (int n = 0; n < count; n++)
	{
		//float min = p_objectList[n]->GetBoundingVolume()->GetMinExtent(p_nAxis),
		//	max = p_objectList[n]->GetBoundingVolume()->GetMaxExtent(p_nAxis),
		//	mid = min + (max - min) * 0.5f;

		if (p_fPartition >= m_pointList[p_objectList[n]].m_vertex.Position[p_nAxis]) p_outLeftList.PushBack(p_objectList[n]);
		else p_outRightList.PushBack(p_objectList[n]);		
	}

	return (int)p_outLeftList.Size();
}

//----------------------------------------------------------------------------------------------
// Distributes the provided triangle list between two objects depending on a the partitioning
// specified by the parameters (Axis, Partition).
//----------------------------------------------------------------------------------------------
int ITreePointCloud::Distribute(const List<int> &p_objectList, float p_fPartition, 
	int p_nAxis, List<int> &p_outLeftList, List<int> &p_outRightList)
{	
	int count = (int)p_objectList.Size();
	for (int n = 0; n < count; n++)
	{
		if (p_fPartition >= m_pointList[p_objectList[n]].m_vertex.Position[p_nAxis]) 
			p_outLeftList.PushBack(p_objectList[n]);
		else
			p_outRightList.PushBack(p_objectList[n]);		
	}

	return (int)p_outLeftList.Size();
}

//----------------------------------------------------------------------------------------------
// Distributes the provided triangle list between two objects depending on which axis-aligned
// bounding box they intersect (left AABB or right AABB).
//----------------------------------------------------------------------------------------------
int ITreePointCloud::Distribute(const List<int> &p_objectList, 
	AxisAlignedBoundingBox &p_leftAABB, AxisAlignedBoundingBox &p_rightAABB, 
	List<int> &p_outLeftList, List<int> &p_outRightList)
{
	int count = (int)p_objectList.Size();	
	Sphere s(Vector3::Zero, m_fSphereRadius);
	for (int n = 0; n < count; n++)
	{
		s.Centre = m_pointList[p_objectList[n]].m_vertex.Position;
		s.ComputeBoundingVolume();
		if (s.GetBoundingVolume()->Intersects(p_leftAABB))
			p_outLeftList.PushBack(p_objectList[n]);

		if (s.GetBoundingVolume()->Intersects(p_rightAABB))
			p_outRightList.PushBack(p_objectList[n]);
	}

	return (int)p_outLeftList.Size();
}

//----------------------------------------------------------------------------------------------
// Returns a partition
//----------------------------------------------------------------------------------------------
float ITreePointCloud::FindPartitionPlane(const List<int> &p_objectList, 
	AxisAlignedBoundingBox &p_aabb, int p_nAxis, PartitionType p_partition) 
{
	switch(p_partition)
	{
		case SurfaceAreaHeuristic:
			return FindPartitionPlaneSAH(p_objectList, p_aabb, p_nAxis);

		case SpatialMedian:
		default:
			return FindPartitionPlaneSpatialMedian(p_objectList, p_aabb, p_nAxis);
	}
}

//----------------------------------------------------------------------------------------------
// Returns a partition based on the spatian median of the object list.
//----------------------------------------------------------------------------------------------
float ITreePointCloud::FindPartitionPlaneSpatialMedian(const List<int> &p_objectList, 
	AxisAlignedBoundingBox &p_aabb, int p_nAxis) 
{
	return p_aabb.GetCentre()[p_nAxis];
}

//----------------------------------------------------------------------------------------------
// Returns a partition baed on the (modified) SAH applied to the object list.
//----------------------------------------------------------------------------------------------
float ITreePointCloud::FindPartitionPlaneSAH(const List<int> &p_objectList, 
	AxisAlignedBoundingBox &p_aabb, int p_nAxis)
{	
	return 0.1f;
}